#pragma once

#include "IDigraph.h"
#include <vector>

class DfsVisitor
{
public:
	DfsVisitor() {};
	virtual ~DfsVisitor() {};
	virtual void initialize(const std::unique_ptr<IDigraph> &graph, int start_vertex) = 0;
	virtual void comeToVertex(int vertex) = 0;
	virtual void processEdge(int from, int to) = 0;
	virtual void leaveVertex(int vertex) = 0;
	virtual void finalize() = 0;
	virtual void preInit(const std::unique_ptr<IDigraph> &graph) = 0;
};

class DfsTopologicalSort : public DfsVisitor
{
public:
	~DfsTopologicalSort() {};
	void initialize(const std::unique_ptr<IDigraph> &graph, int start_vertex);
	void comeToVertex(int vertex);
	void processEdge(int from, int to);
	void leaveVertex(int vertex);
	void finalize();
	bool isVisited(int vertex);
	bool hasLoop();
	void preInit(const std::unique_ptr<IDigraph> &graph);
	std::vector<Edge> getProcessOrder();
	std::vector<int> getSortedOrder();
private:
	std::vector<bool> _visited_vertices;
	std::vector<bool> _on_stack;
	std::vector<bool> _global_visited;
	std::vector<int> _sorted_order;
	std::vector<Edge> _edge_process_order;
	bool _has_loop;
};

class DfsTarjan : public DfsVisitor
{
public:
	~DfsTarjan() {};
	void initialize(const std::unique_ptr<IDigraph> &graph, int start_vertex);
	void comeToVertex(int vertex);
	void processEdge(int from, int to);
	void leaveVertex(int vertex);
	void finalize();
	void preInit(const std::unique_ptr<IDigraph> &graph);
	std::vector<std::vector<int> > getStronglyConnectedComponents(const std::unique_ptr<IDigraph> &graph);
	std::unique_ptr<IDigraph> getCondesedGraph(const std::unique_ptr<IDigraph> &graph);
	std::vector<int> getExactComponent(const std::unique_ptr<IDigraph> &graph, int vertex);
	std::vector<int> getSortedCondesedGraph(const std::unique_ptr<IDigraph> &graph);
	std::vector<int> getVerticesColors(const std::unique_ptr<IDigraph> &graph);
private:
	std::vector<int> _in_times;
	std::vector<int> _farthest;
	std::vector<std::vector<int>> _components;
	std::vector<int> _buffer;
	std::vector<bool> _buffered;
	std::vector<int> _ancestor;
	int _cur_time;
};